package hot_problems_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P13_0056 {
    /*
    * 合并区间，返回一个新的区间数组
    *   1 <= intervals.length <= 1e4
    *   每个区间[start, end]满足约束：
    *   0 <= start <= end <= 1e4
    * */
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        int left = intervals[0][0];
        int right = intervals[0][1];
        int new_left, new_right;
        for(int i=1; i<intervals.length; i++){
            new_left = intervals[i][0];
            new_right = intervals[i][1];
            if(new_left > right){
                list.add(new int[]{left, right});
                left = new_left;
                right = new_right;
            } else {
                right = Math.max(right, new_right);
            }
        }
        list.add(new int[]{left, right});
        int[][] res = new int[list.size()][2];
        for(int i=0; i<list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }

    /*
    * 原地存储结果，无需再使用List
    * */
    public int[][] merge_better(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));
        int left = intervals[0][0];
        int right = intervals[0][1];
        int new_left, new_right;
        int res_count = 0;
        for(int i=1; i<intervals.length; i++){
            new_left = intervals[i][0];
            new_right = intervals[i][1];
            if(new_left > right){
                intervals[res_count][0] = left;
                intervals[res_count][1] = right;
                res_count ++;
                left = new_left;
                right = new_right;
            } else {
                right = Math.max(right, new_right);
            }
        }
        intervals[res_count][0] = left;
        intervals[res_count][1] = right;
        res_count ++;
        int[][] res = new int[res_count][2];
        for(int i=0; i<res_count; i++){
            res[i] = intervals[i];
        }
        return res;
    }
}
